# 给一非空的单词列表，返回前 k 个出现次数最多的单词。
#  返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
#
#  示例 1：
# 输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
# 输出: ["i", "love"]
# 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
#     注意，按字母顺序 "i" 在 "love" 之前。
#
#  示例 2：
# 输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"],
# k = 4
# 输出: ["the", "is", "sunny", "day"]
# 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
#     出现次数依次为 4, 3, 2 和 1 次。
import heapq
from typing import List
from collections import Counter


class Solution:

    def topKFrequent2(self, words: List[str], k: int) -> List[str]:
        """
        堆
        :param words:
        :param k:
        :return:
        """
        class WordWithFrequent:
            def __init__(self, word, frequent):
                self.word = word
                self.frequent = frequent

            def __lt__(self, other):
                if self.frequent != other.frequent:
                    return self.frequent < other.frequent
                else:
                    return self.word > other.word
        wordCount = Counter(words)
        heap = []
        for word, count in wordCount.items():
            heapq.heappush(heap, WordWithFrequent(word, count))
            if len(heap) > k:
                heapq.heappop(heap)

        return [e.word for e in sorted(heap, reverse=True)]

    def topKFrequent1(self, words: List[str], k: int) -> List[str]:
        """
        桶排序
        首先统计各个单词的次数
        然后以次数为下标分别装入各个桶中
        然后从后向前遍历桶直到结果集为k个
        :param words:
        :param k:
        :return:
        """
        wordToCount = Counter(words)
        bucket = [None] * len(words)
        for word, count in wordToCount.items():
            if bucket[count]:
                bucket[count].append(word)
            else:
                bucket[count] = [word]
        res = []
        index = -1
        while k > 0:
            tmpList = bucket[index]
            if tmpList:
                size = len(tmpList)
                tmpList.sort()
                if k - size >= 0:
                    res.extend(tmpList)
                    k -= size
                else:
                    res.extend(bucket[index][0:k])
                    k = 0
            index -= 1
        return res

    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        return self.topKFrequent2(words, k)


if __name__ == "__main__":
    words = ["i", "love", "leetcode", "i", "love", "coding"]
    k = 2

    words = ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"]
    k = 4
    print(Solution().topKFrequent(words, k))
